﻿通用CORDIC算法是一种用于计算包括三角函数在内的初等函数的数值算法。由于计算过程只需要加法运算和位移运算，而且通过迭代来减少误差（渐近稳定），所以特别适合于没有独立乘法器的中低端单片机或IP核。本文描述了一个用Verilog实现的可综合的通用CORDIC算法核心，希望以此能帮助特定厂商和电子爱好者解决所面临的实际问题。

1959年Jake E.
Volder为了解决美国空军B58型轰炸机导航计算机的设计问题，提出了利用几何方法求解正弦和余弦函数的数值方法。具体做法是通过一个可以在直角坐标系单位圆上旋转的向量$\vec{v}$，并规定向量每次迭代所旋转的角度$\Delta\theta_{i}$满足

\begin{equation}
	\label{eq_gammai_shift}
	\tan\Delta\theta_{i} = \sigma_{i}2^{-i}
\end{equation}

其中，$\sigma_{i} \in
\{-1,1\}, i \in
\mathbb{N}$。当向量沿逆时针旋转时，$\sigma_{i}=1$，当向量沿顺时针旋转时$\sigma_{i}=-1$。

设$\vec{v}$是以坐标原点为起点，终点为单位圆上任意一点的向量，其与x轴正方向夹角为$\beta$，则该向量旋转$\Delta\theta_{i}$之后所得到的新向量为

\begin{equation}
	\begin{split}
		\vec{v_{i+1}} &= R_{i}\vec{v_{i}} \\
		&= \begin{bmatrix}
			\cos\Delta\theta_{i} & -\sin\Delta\theta_{i} \\
			\sin\Delta\theta_{i} & \cos\Delta\theta_{i} \\
		\end{bmatrix}\vec{v_{i}}
	\end{split}
\end{equation}

旋转后向量$\vec{v}$与x轴正方向的夹角为

\begin{equation}
	\label{eq_iteration_betachange}
	\beta_{i+1} = \beta_{i} + \sigma_{i}|\Delta\theta_{i}|
\end{equation}

其中，$\Delta\theta_{i} =
\sigma_{i}\arctan2^{-i}$。$R_{i}$被称为旋转矩阵。当向量$\vec{v}$被限制在仅能于第一和第四象限活动时，通过三角恒等式

\begin{equation}
	\cos\alpha = \frac{1}{\sqrt{1+\tan^{2}\alpha}}
\end{equation}

\begin{equation}
	\sin\alpha = \frac{\tan\alpha}{\sqrt{1+\tan^2\alpha}}
\end{equation}

可以得到

\begin{equation}
	\label{eq_cordic_tanformat}
	\begin{split}
		\vec{v_{i+1}} &= \frac{1}{\sqrt{1+\tan^2\Delta\theta_{i}}}\begin{bmatrix}
			1 & -\tan\Delta\theta_{i} \\
			\tan\Delta\theta_{i} & 1 \\
		\end{bmatrix}\vec{v_{i}} \\
	\end{split}
\end{equation}

将等式$\ref{eq_gammai_shift}$代入等式$\ref{eq_cordic_tanformat}$可得

\begin{equation}
	\label{eq_cordic_final}
	\begin{split}
		\vec{v_{i+1}} &= R_{i}\vec{v_{i}} \\ 
			&= K_{i}R_{i}^{'}\vec{v_{i}} \\ 
			&= \frac{1}{\sqrt{1+2^{-2i}}}\begin{bmatrix}
			1 & -\sigma_{i}2^{-i} \\
			\sigma_{i}2^{-i} & 1 \\
		\end{bmatrix}\vec{v_{i}}
	\end{split} 
\end{equation}

其中

\begin{equation}
	K_{i} = \frac{1}{\sqrt{1+2^{-2i}}}
\end{equation}

请注意等式$\ref{eq_cordic_final}$中的$R_{i}^{'}\vec{v_{i}}$项。由于乘以或除以$2$等价于左移或右移运算，通过$N$次迭代，最终的结果$\vec{v_{T}}$如下所示

\begin{equation}
	\label{eq_shift_vn}
	\begin{split}
	\vec{v_{T}} &= \left(\prod_{i=0}^{N-1}
	K_{i}\right)\left(\prod_{i=N-1}^{0}R_{i}^{'}\right)\vec{v_{0}} \\
	&= \left(\prod_{i=0}^{N-1}K_{i}\right)\vec{v_{T}^{'}}
	\end{split}
\end{equation}

现在唯一的遗留问题是如何处理$K$。一般情况下，CORDIC算法使用有限步骤迭代，而不使用有限误差迭代。主要原因是一旦指定了迭代的次数，参数$K$就会从一个变量退化为一个常数，即

\begin{equation}
	K = \prod_{i=0}^{N-1} \frac{1}{\sqrt{1+2^{-2i}}}
\end{equation}

一般情况下，迭代40次即可使结果包含10个有效数字。以此为例只需设初始向量$\vec{v_{0}} = \begin{bmatrix}0.6072529350 & 0 & \alpha \end{bmatrix}^{T}$，运算结束以后向量$\vec{v_{T}^{'}}$就保存有正确的三角函数值了。
